package likou.bfs;

import java.util.*;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/28 21:45
 */
public class _752 {
    public static void main(String[] args) {
        System.out.println(openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
    }

    public static int openLock(String[] deadends, String target) {
        Set<String> dontSet = new HashSet<>();
        Collections.addAll(dontSet, deadends);
        if (dontSet.contains("0000") || dontSet.contains(target)) {
            return -1;
        }
        if ("0000".equals(target)) {
            return 0;
        }

        Set<String> leftSet = new HashSet<>();
        Set<String> rightSet = new HashSet<>();

        Deque<String> leftNowDeque = new LinkedList<>();
        Deque<String> rightNowDeque = new LinkedList<>();

        leftSet.add("0000");
        rightSet.add(target);

        leftNowDeque.offer("0000");
        rightNowDeque.offer(target);

        int res = 1;
        while (!leftNowDeque.isEmpty()) {
            int n = leftNowDeque.size();
            for (int i = 0; i < n; i++) {
                String now = leftNowDeque.poll();
                if (bfs(dontSet, leftNowDeque, leftSet, rightSet, now)) {
                    return res;
                }
            }
            res++;
            n = rightNowDeque.size();
            for (int i = 0; i < n; i++) {
                String now = rightNowDeque.poll();
                if (bfs(dontSet, rightNowDeque, rightSet, leftSet, now)) {
                    return res;
                }
            }
            res++;
        }

        return -1;
    }

    private static boolean bfs(Set<String> dontSet, Deque<String> leftNowDeque, Set<String> leftSet, Set<String> rightSet, String now) {
        char[] chars = now.toCharArray();
        for (int i = 0; i < 4; i++) {
            char old = chars[i];
            if (chars[i] == '9') {
                chars[i] = '0';
            } else {
                chars[i]++;
            }
            String up = String.valueOf(chars);
            chars[i] = old;//回退

            if (!dontSet.contains(up) && !leftSet.contains(up)) {
                if (rightSet.contains(up)) {
                    return true;
                }
                leftNowDeque.offer(up);
                leftSet.add(up);
            }


            if (chars[i] == '0') {
                chars[i] = '9';
            } else {
                chars[i]--;
            }
            String down = String.valueOf(chars);
            chars[i] = old;//回退

            if (!dontSet.contains(down) && !leftSet.contains(down)) {
                if (rightSet.contains(down)) {
                    return true;
                }
                leftNowDeque.offer(down);
                leftSet.add(down);
            }
        }


        return false;
    }


    public int openLock2(String[] deadends, String target) {
        Queue<Integer> q1 = new LinkedList<>();
        int[] v1 = new int[10000];
        int[] v2 = new int[10000];
        int di, end = Integer.parseInt(target);
        for (String s : deadends) {
            di = Integer.parseInt(s);
            v1[di] = v2[di] = -1;
        }
        if (v1[0] == -1 || v1[end] == -1) return -1;
        if (end == 0) return 0;
        Queue<Integer> q2 = new LinkedList<>();

        q1.add(0);
        v1[0] = 1;
        q2.add(end);
        v2[end] = 1;
        Queue<Integer> qt = null;
        int[] vt;
        int step = 0;
        int[] num = new int[]{1, 10, 100, 1000};
        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.size() > q2.size()) {

                q1 = q2;
                q2 = qt;
                vt = v1;
                v1 = v2;
                v2 = vt;
            }
            qt = new LinkedList<>();
            while (!q1.isEmpty()) {
                int now = q1.poll();
                for (int i = 0; i < 4; i++) {
                    int point = (now / num[i]) % 10;
                    for (int j = 9; j <= 11; j += 2) {
                        int ans = now + ((point + j) % 10 - point) * num[i];
                        if (v2[ans] == 1) return step + 1;
                        if (v1[ans] != 0) continue;

                        qt.add(ans);
                        v1[ans] = 1;
                    }
                }
            }
            q1 = qt;
            step++;


        }
        return -1;
    }

}
